1. Field
The present invention relates generally to compilers and, more specifically, to the performance improvement of a Just-In-Time compiler in a Java Virtual Machine by dynamically optimizing division operations.
2. Description
Currently, the Java programming language is more commonly used for building network-based software than other languages such as C and C++ because of its platform-independent characteristics. The use of a Java Virtual Machine (JVM) makes Java independent from different hardware and operating systems. JVM is an abstract computing machine implemented in software on top of a hardware platform and operating system. In order to use a JVM, a Java program must first be compiled into an architecture-neutral distribution format, called Java bytecode. JVM interprets the bytecode and executes the code on a specific computing platform. However, the interpretation by JVM typically imposes an unacceptable performance penalty to the execution of a bytecode because of large runtime overhead processing. A Just-In-Time (JIT) compiler has been designed to improve the JVM's performance. It compiles the bytecode of a given method into a native code of the underlying machine before the method is first called. The native code of the method is stored in memory and any later calls to the method will be handled by this faster native code, instead of by the JVM's interpretation.
Although the JIT compiler can usually speed up the execution of a Java program, optimization methods are needed for a JIT compiler to generate a more efficient native code for a Java bytecode. For example, one optimization method is to inline some simple methods to reduce the method invocation overhead. Another optimization method is to speed up integer division operations that are normally very expensive.
One method for speeding up integer division operations in processors in general is to implement them using integer multiplications, which are several times faster than corresponding divisions. However, it usually requires that the divisor have certain characteristics. For example, T. Granlund and P. Montgomery teach a method for speeding up an integer division with an invariant divisor by converting the division into a multiplication operation of the dividend and the reciprocal of the divisor in “Division by Invariant Integers using Multiplication”, Proceedings of the 1994 Associates of Computing Machinery (ACM) Special Interest Group on Programming Languages (SIGPLAN) Conference on Programming Language Design and Implementation (Granlund hereinafter). This method requires that the divisor be a known constant at compilation time and thus results in a static optimization approach for divisions. In reality, however, divisors may not be known until runtime. Therefore, dynamic approaches are necessary to optimize integer divisions at runtime.